﻿#include <iostream>
#include <deque>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存下标，保证队列是单调递减的
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // 删除窗口外的元素
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // 保证队列从大到小
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);

        // 记录结果
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int v : res) cout << v << " "; // 输出：3 3 5 5 6 7
    return 0;
}
